Действие перестановки

Перестановкой из $S_n$ можно подействовать на любое $n$-элементное множество $A$, если элементы $A$ естественным образом линейно упорядочены.

Перестановка $\theta \in S_n$ называется **сортирующей** для слова $w$ длины $n$ над упорядоченным алфавитом $\Sigma$, если $\theta(w)[i] \leq \theta(w)[j]$ для любых $i < j$.

Перестановка $\theta \in S_n$ называется **стабильно сортирующей** для $w$, если $\theta$ не меняет порядок равных букв. Для любых $i < j$ таких, что $w[i] = w[j]$, выполнено $\theta(w)[i] < \theta(w)[j]$.